Editing graphs to satisfy degree constraints: a parameterized approach

Title: Editing graphs to satisfy degree constraints: a parameterized approach
Creator: Mathieson, Luke; Szeider, Stefan
Relation: Journal of Computer and System Sciences Vol. 78, Issue 1, p. 179-191
Publisher Link: http://dx.doi.org/10.1016/j.jcss.2011.02.001
Publisher: Academic Press
Resource Type: journal article
Date: 2012
Description: We study a wide class of graph editing problems that ask whether a given graph can be modified to satisfy certain degree constraints, using a limited number of vertex deletions, edge deletions, or edge additions. The problems generalize several well-studied problems such as the General Factor Problem and the Regular Subgraph Problem. We classify the parameterized complexity of the considered problems taking upper bounds on the number of editing steps and the maximum degree of the resulting graph as parameters.
Subject: parameterized complexity; computational complexity; kernelization; graph editing; regular subgraph; general factor
Identifier: http://hdl.handle.net/1959.13/1311668
Identifier: uon:22255
Identifier: ISSN:0022-0000
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format